Maximum difference between node and ancestor [DFS]

Time: O(N); Space: O(H); medium

Given the root of a binary tree, find the maximum value V

for which there exists different nodes A and B where V = |A.val - B.val| and A is an ancestor of B.

(A node A is an ancestor of B if either: any child of A is equal to B, or any child of A is an ancestor of B.)

Example 1:

Input: root = {TreeNode} [8,3,10,1,6,null,14,null,null,4,7,13]

Output: 7

Explanation:

  • We have various ancestor-node differences, some of which are given below :

  • |8 - 3| = 5

  • |3 - 7| = 4

  • |8 - 1| = 7

  • |10 - 13| = 3

  • Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.

Constraints:

  • The number of nodes in the tree is between 2 and 5000.

  • Each node will have value between 0 and 100000.

Hints:

  1. For each subtree, find the minimum value and maximum value of its descendants.

[1]:

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

1. Iterative stack solution

[2]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(H)
    """
    def maxAncestorDiff(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        result = 0
        stack = [(root, 0, float("inf"))]

        while stack:
            node, mx, mn = stack.pop()
            if not node:
                continue
            result = max(result, mx-node.val, node.val-mn)
            mx = max(mx, node.val)
            mn = min(mn, node.val)
            stack.append((node.left, mx, mn))
            stack.append((node.right, mx, mn))

        return result

[3]:

s = Solution1()

root = TreeNode(8)
root.left, root.right = TreeNode(3), TreeNode(10)
root.left.left, root.left.right = TreeNode(1), TreeNode(6)
root.right.right = TreeNode(14)
root.right.right.left = TreeNode(8)
root.left.right.left, root.left.right.right = TreeNode(4), TreeNode(7)
assert s.maxAncestorDiff(root) == 7

2. Recursive solution

[4]:

class Solution2(object):
    def maxAncestorDiff(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def maxAncestorDiffHelper(node, mx, mn):
            if not node:
                return 0

            result = max(mx-node.val, node.val-mn)
            mx = max(mx, node.val)
            mn = min(mn, node.val)

            result = max(result, maxAncestorDiffHelper(node.left, mx, mn))
            result = max(result, maxAncestorDiffHelper(node.right, mx, mn))

            return result

        return maxAncestorDiffHelper(root, 0, float("inf"))

[5]:

s = Solution2()

root = TreeNode(8)
root.left, root.right = TreeNode(3), TreeNode(10)
root.left.left, root.left.right = TreeNode(1), TreeNode(6)
root.right.right = TreeNode(14)
root.right.right.left = TreeNode(8)
root.left.right.left, root.left.right.right = TreeNode(4), TreeNode(7)
assert s.maxAncestorDiff(root) == 7